package com.ai.zuochengyun.phase01.class03;

import java.util.*;

/**
 * 查找对低公共祖先
 */
public class Code25_LowerAncestor {

    public static BinaryTreeNode getLowerAncestor1(BinaryTreeNode x, BinaryTreeNode a, BinaryTreeNode b) {
        // 保存当前节点的父节点
        Map<BinaryTreeNode, BinaryTreeNode> parentMap = new HashMap<>();
        parentMap.put(x, null);
        fillParentMap(x, parentMap);

        Set<BinaryTreeNode> oldSet = new HashSet<>();
        BinaryTreeNode cur = a;
        oldSet.add(cur);
        while (parentMap.get(cur) != null) {
            // 父节点
            cur = parentMap.get(cur);
            oldSet.add(cur);
        }

        // 重定向到b节点，然后判断是否存在oldSet中，如果存在，说明有交集
        cur = b;
        while (!oldSet.contains(cur)) {
            cur = parentMap.get(cur);
        }
        return cur;
    }

    private static void fillParentMap(BinaryTreeNode head, Map<BinaryTreeNode, BinaryTreeNode> parentMap) {
        if (head.left != null) {
            parentMap.put(head.left, head);
            fillParentMap(head.left, parentMap);
        }
        if (head.right != null) {
            parentMap.put(head.right, head);
            fillParentMap(head.right, parentMap);
        }
    }

    public static BinaryTreeNode getLowerAncestor2(BinaryTreeNode x, BinaryTreeNode a, BinaryTreeNode b) {
        return process(x, a, b).ans;
    }

    private static Info process(BinaryTreeNode x, BinaryTreeNode a, BinaryTreeNode b) {
        if (x == null) {
            return new Info(false, false, null);
        }

        // 向左树要信息，向右树要信息
        Info leftInfo = process(x.left, a, b);
        Info rightInfo = process(x.right, a, b);

        // X是a，或者左边发现了a，或者右边发现了a
        boolean findA = x == a || leftInfo.findA || rightInfo.findA;
        // X是b，或者左边发现了b，或者右边发现了b
        boolean findB = x == b || leftInfo.findB || rightInfo.findB;

        BinaryTreeNode ans = null;
        // 没有在X处汇聚，有两种情况，以X为头的左树找到了答案，以X为头的右树找到了答案
        // 左树找到了答案
        if (leftInfo.ans != null) {
            ans = leftInfo.ans;
        }
        // 右树找到了答案
        else if (rightInfo.ans != null) {
            ans = rightInfo.ans;
        }
        // 在X处汇聚了
        else {
            if (findA && findB) {
                ans = x;
            }
        }
        return new Info(findA, findB, ans);
    }


    public static class Info {
        public boolean findA;

        public boolean findB;

        public BinaryTreeNode ans;

        public Info(boolean findA, boolean findB, BinaryTreeNode ans) {
            this.findA = findA;
            this.findB = findB;
            this.ans = ans;
        }
    }
}
